/**
 * xarray.c
 * xarray 用户程序版本简易实现
 * 
 * 竹影半墙
 * 2023.08
 */
#include "base.h"
#include "xarray.h"

struct xy_xrange {
    uint64_t *x;
    int direct;
    int step;
};

#define xys_xrange_not(v,o,n) __sync_bool_compare_and_swap(v,o,n)
#define xy_arrays(a) ({sizeof(a) / sizeof((a)[0]);})
#define xys_xrange_define(xs, rg)       \
    struct xy_xrange x##rg[] = {        \
        {&xs->x,     0,           1},   \
        {&xs->x_max, XY_SLOTS-1, -1},   \
    };
#define XY_CACHE_MAX (2)

#if 0
#endif
static __always_inline bool xy_cant_shrink(struct xy_node *n)
{
    return !n->l_exp || !n->slot[0] || 1 != n->s_use;
}

static __always_inline void xy_leaf_zero(struct xy_node *n)
{
    if (!n->l_exp)
        memset(n->s_value, 0, XY_LEAF_VLEN);
    return ;
}

static __always_inline uint64_t xy_ts_to_ns(struct timespec ts)
{
    return ts.tv_sec*1000000000 + ts.tv_nsec;
}

static __always_inline 
void xy_top_set(struct xarray *xy, struct xy_node *n)
{
    xy->head &= ~XY_TOP_MASK;
    xy->head |= (uintptr_t)n;
    return ;
}

static __always_inline 
struct xy_node * xy_top_get(struct xarray *xy)
{
    return (struct xy_node*)(xy->head&XY_TOP_MASK);
}

static __always_inline void xy_cache_set(struct xarray *xy)
{
    xy->head |= 1ull << XY_CACHE_SHIFT;
    return ;
}

static __always_inline bool xy_cache_get(struct xarray *xy)
{
    return (bool)(xy->head & (1ull << XY_CACHE_SHIFT));
}

static __always_inline void xy_heap_set(struct xarray *xy)
{
    xy->head |= 1ull << XY_HEAP_SHIFT;
    return ;
}

static __always_inline bool xy_heap_get(struct xarray *xy)
{
    return (bool)(xy->head & (1ull << XY_HEAP_SHIFT));
}

static __always_inline void xy_leaf_set(struct xy_node *n, uint8_t slot)
{
    *n->s_value |= 1ull << slot;
    return ;
}

static __always_inline bool xy_leaf_get(struct xy_node *n, uint8_t slot)
{
    return (bool)(*n->s_value & (1ull << slot));
}

static __always_inline void xy_leaf_clear(struct xy_node *n, uint8_t slot)
{
    *n->s_value &= ~(1ull << slot);
    return ;
}

static __always_inline bool xys_leaf_get(struct xy_state *xs)
{
    bool iset;
    struct xy_node *n = xs->node;

    iset = false;
    if (n && !n->l_exp)
        iset = (bool)(*n->s_value & (1ull << xs->s_idx));
    return iset;
}

#if 0
#endif
enum xy_lock_e
{
    XY_LOCKR = 0,
    XY_LOCKW = 1,
    XY_LOCKN = 2
};

static __always_inline int
xy_lock_none  (xy_lock_t *lock){return 0;}
static __always_inline int
xy_unlock_none(xy_lock_t *lock){return 0;}

static xy_lock_f  xy_locke[] = {
    pthread_rwlock_rdlock,
    pthread_rwlock_wrlock,
    xy_lock_none
};
static xy_lock_f xy_unlocke[] = {
    pthread_rwlock_unlock,
    pthread_rwlock_unlock,
    xy_unlock_none
};

static __always_inline int 
xy_lock(struct xarray *xy, enum xy_lock_e ei)
{
    xy_lock_f lock = xy_locke[ei];
    return lock(&xy->lock);
}

static __always_inline int 
xy_unlock(struct xarray *xy, enum xy_lock_e ei)
{
    xy_lock_f unlock = xy_unlocke[ei];
    return unlock(&xy->lock);
}

#if 0
#endif
static struct pageca xy_ca = {
    {
        .size = XY_HEAPCA_LEN,
        .max  = (1u<<12)/XY_HEAPCA_LEN+1,
        .num  = 0,
        .head = NULL
    },
    NULL, NULL, 0
};
__attribute__((constructor))
static void xy_ca_init(void)
{
    pca_init(&xy_ca);
    return ;
}

__attribute__((destructor))
static void xy_ca_close(void)
{
    pca_close(&xy_ca);
    return ;
}

static __always_inline struct xarray * xy_palloc(void)
{
    struct xarray *xy;
    void *a;

    a = pca_alloc(&xy_ca);
    if (unlikely(!a))
        return a;
    xy = (struct xarray *)a;
    memset(xy, 0, pca_size(&xy_ca));
    xy_cache_set(xy);
    return xy;
}

static __always_inline struct xarray * xy_malloc(void)
{
    void *a;
    struct xarray *xy;
    size_t size = sizeof(*xy);

    a = malloc(size);
    if (unlikely(!a))
        return a;
    xy = (struct xarray*)a;
    xy->head = 0;
    xy_heap_set(xy);
    return xy;
}

static struct xarray *
xy_tryalloc(struct xarray *xy, unsigned flag)
{
    if (unlikely(NULL != xy)) {
        xy->head = 0;
        return xy;
    }
    if ((flag != XY_CACHE_NONE) &&
        (xy = xy_palloc()))
        return xy;
    return xy_malloc();
}

static uint64_t xy_cache_full(uint64_t ca)
{
    uint32_t leaves, nodes = 0;
    int le = 0;

    while ((ca>>le) >= XY_SLOTS) {
        nodes += 1u<<le;
        le += XY_LEVEL_EXP;
    }
    leaves = ca / XY_SLOTS + 1;
    return ((uint64_t)nodes<<32) | leaves;
}

static uint64_t 
xy_cache_calc(struct xarray *xy, unsigned flag, uint64_t ca)
{
    uint64_t calc;

    switch (flag)
    {
    case XY_CACHE_FULL:
        calc = xy_cache_full(ca);
        break;
    case XY_CACHE_MAX:
        calc = ca;
        break;
    default:
        calc = 0;
        break;
    }
    return calc;
}

static void 
xy_node_cache_init(struct xarray *xy, unsigned flag, uint64_t ca)
{
    int i;
    struct pageca *pa;
    uint64_t calc;

    calc = xy_cache_calc(xy, flag, ca);
    if (!calc)
        return ;
    for (i = 0; i < XY_CACHE_MAX; ++i) {
        pa = xy->ca + i;
        pca_app(pa,
            !i ? sizeof(struct xy_node) : XY_LEAF_LEN,
            !i ? (uint32_t)(calc>>32):(uint32_t)calc);
        pca_init(pa);
    }
    return ;
}

#if 0
#endif
static struct xy_node * xy_node_alloc(struct xarray *xy, uint8_t le)
{
    struct xy_node *n;
    size_t size;

    if (!xy_cache_get(xy)) {
        size = le ? sizeof(struct xy_node) : XY_LEAF_LEN;
        return (struct xy_node*)malloc(size);
    }
    n = le ? 
        (struct xy_node *)pca_alloc(xy_canode(xy)):
        (struct xy_node *)pca_alloc(xy_caleaf(xy));
    return n;
}

static struct xy_node *
xys_alloc(struct xy_state *xs, uint8_t le)
{
    struct xy_node *n;

    n = xy_node_alloc(xs->xy, le);
    if (unlikely(!n)) {
        xys_error_set(xs, -1);
        return n;
    }
    memset(n->slot,0,sizeof(n->slot));
    n->parent = xs->node;
    n->l_exp = le;
    n->s_use = 0;
    xy_leaf_zero(n);
    return n;
}

static void xys_free(struct xy_state *xs, struct xy_node *n)
{
    struct xarray *xy = xs->xy;

    if (!xy_cache_get(xy)) {
        free(n);
        return ;
    }
    if (n->l_exp) {
        pca_free(xy_canode(xy), n);
        return ;
    }
    pca_free(xy_caleaf(xy), n);
    return ;
}

#if 0
#endif
static void * 
xys_descend(struct xy_state *xs, struct xy_node *n)
{
    unsigned i = (xs->x >> n->l_exp)&XY_SLOTS_MOD;

    xs->node  = n;
    xs->s_idx = i;
    return n->slot[i];
}

static __always_inline uint64_t xys_xmax(struct xy_node *n)
{
    return (XY_SLOTS << n->l_exp) - 1;
}

static int 
xy_xlevel_exp(uint64_t x, struct xy_node *t, struct xy_node **n)
{
    int le = 0;

    *n = t;
    if (!t) {
        while ((x>>le) >= XY_SLOTS)
            le += XY_LEVEL_EXP;
        return le + XY_LEVEL_EXP;
    }
    le = t->l_exp + XY_LEVEL_EXP;
    return le;
}

static int xys_expand(struct xy_state *xs, struct xy_node *t)
{
    int le;
    struct xy_node *n;
    uint64_t x = xs->x;

    xs->node = NULL;
    le = xy_xlevel_exp(x, t, &n);
    if (!n)
        return le;
    while (x > xys_xmax(t)) {
        n = xys_alloc(xs, le);
        if (unlikely(!n))
            return -1;
        n->slot[0] = t;
        n->s_use  += 1;
        t->parent = n;
        t->n_idx  = 0;

        t = n;
        le += XY_LEVEL_EXP;
    }
    xy_top_set(xs->xy, n);
    xs->node = n;
    return le;
}

static void 
xys_parent_update(struct xarray *xy, void **s, struct xy_node *n)
{
    void **start;
    struct xy_node *p;

    if (&xy->head == (void*)s) {
        xy_top_set(xy, n);
        return ;
    }

    *s = n;
    p  = n->parent;
    start = (void**)p->slot;
    n->n_idx = s - start;
    p->s_use += 1;
    return ;
}

static void * xys_create(struct xy_state *xs)
{
    struct xy_node *n;
    struct xy_node *c;
    void **s;
    int le;
    struct xarray *xy = xs->xy;

    le = xys_expand(xs, xy_top_get(xy));
    if (xys_error(xs))
        return NULL;
    s = (void**)&xy->head;
    c = xy_top_get(xy);

    while (le > 0) {
        le -= XY_LEVEL_EXP;
        if (c)
            n = c;
        else if ((n=xys_alloc(xs,le)))
            xys_parent_update(xy,s,n);
        else
            break;
        c = xys_descend(xs, n);
        s = (void**)(n->slot + xs->s_idx);
    }
    return c;
}

static __always_inline uint64_t xys_timens(void)
{
    struct timespec ts;
    clock_gettime(CLOCK_MONOTONIC, &ts);
    return xy_ts_to_ns(ts);
}

static void 
xys_sleep(struct xy_state *xs, uint64_t *t_last, enum xy_lock_e lei)
{
    struct timespec ts;
    struct xarray *xy;
    uint64_t tns;
    uint64_t t_max_ns = xs->t_max_ns;
    uint64_t t_sleep_ns = xs->t_sleep_ns;

    if (!t_sleep_ns || !t_max_ns)
        return ;

    if (*t_last+t_max_ns <= (tns=xys_timens())) {
        xy = xs->xy;
        xy_unlock(xy, lei);

        ts.tv_sec  = t_sleep_ns / 1000000000;
        ts.tv_nsec = t_sleep_ns % 1000000000;
        nanosleep(&ts, NULL);

        *t_last = tns + xy_ts_to_ns(ts);
        xy_lock(xy, lei);
    }
    return ;
}

static bool xys_slot_empty(struct xy_node *n, uint8_t s_idx)
{
    if (n->slot[s_idx])
        return false;
    if (!n->l_exp && xy_leaf_get(n, s_idx))
        return false;
    return true;
}

static void xys_xrange(struct xy_state *xs, uint64_t *t_last)
{
    struct xarray *xy;
    xys_xrange_define(xs, rg);
    int i, k, step;
    struct xy_node *n;
    uint64_t x = 0;

    i = 0;
    xy = xs->xy;

    x_boundary:
    for (x = 0, step = xrg[i].step,
         n = xy_top_get(xy); n;/**/) {

        for (k = xrg[i].direct;
             k>=0 && k<XY_SLOTS &&
             xys_slot_empty(n,k);
             k += step) {

            ;/* none */
        }
        assert(k>=0 && k<XY_SLOTS);
        x += k << n->l_exp;

        if (!n->l_exp)
            break;
        n = n->slot[k];
        xys_sleep(xs, t_last, XY_LOCKR);
    }
    * xrg[i].x = x;
    if (++i < xy_arrays(xrg))
        goto x_boundary;

    return ;
}

static void xys_shrink(struct xy_state *xs)
{
    struct xy_node *c;
    struct xarray  *xy;
    struct xy_node *n = xs->node;

    xy = xs->xy;
    for (;;) {
        if (xy_cant_shrink(n))
            break;
        c = n->slot[0];
        c->parent = NULL;
        xy_top_set(xy, c);
        xys_free(xs, n);

        n = c;
    }
    return ;
}

static void xys_del_node(struct xy_state *xs)
{
    struct xarray *xy;
    uint8_t i;
    struct xy_node *p;
    struct xy_node *n = xs->node;

    xy = xs->xy;
    for (;;) {
        if (!n || n->s_use)
            break;
        p = n->parent;
        if (p) {
            i = n->n_idx;
            p->slot[i] = NULL;
            p->s_use -= 1;
        }
        xys_free(xs, n);
        n = p;

        xs->node = n;
    }
    if (!n) {
        xy_top_set(xy, 0);
        return ;
    }
    if (n->parent)
        return ;
    xys_shrink(xs);
    return ;
}

static void * xys_get_nolock(struct xy_state *xs)
{
    void *y;
    struct xy_node *n = xy_top_get(xs->xy);

    y = xs->node = NULL;
    while (n) {
        if (!n->l_exp) {
            y = xys_descend(xs, n);
            break;
        }
        n = xys_descend(xs, n);
    }
    return y;
}

static bool 
xys_no_value(struct xy_state *xs, void **y)
{
    *y = xys_get_nolock(xs);
    if (xys_leaf_get(xs))
        return false;
    return true;
}

#if 0
#endif
void * xys_add(struct xy_state *xs, void *y)
{
    void *yo;
    uint8_t i;
    struct xy_node *n;
    struct xarray *xy = xs->xy;

    xy_lock(xy, XY_LOCKW);

    xys_error_set(xs,0);
    yo = xys_create(xs);
    if ( xys_error (xs))
        goto addend;

    n = xs->node;
    i = xs->s_idx;
    n->slot[i]= y;
    if (!xy_leaf_get(n,i)) {
        xy_leaf_set(n, i);
        n->s_use += 1;
        yo = y;
    }
addend:
    xy_unlock(xy, XY_LOCKW);
    return yo;
}

void * xys_get(struct xy_state *xs)
{
    void *y;
    struct xarray *xy = xs->xy;

    xy_lock(xy, XY_LOCKR);
    y = xys_get_nolock(xs);
    xy_unlock(xy, XY_LOCKR);
    return y;
}

void * xys_del(struct xy_state *xs)
{
    void *y;
    uint8_t i;
    struct xy_node *n;
    struct xarray *xy = xs->xy;

    xy_lock(xy, XY_LOCKW);
    if (xys_no_value(xs, &y))
        goto delend;
    n = xs->node;
    i = xs->s_idx;
    n->slot[i] = NULL;
    n->s_use  -= 1;
    xy_leaf_clear(n, i);
    xys_del_node(xs);
delend:
    xy_unlock(xy, XY_LOCKW);
    return y;
}

void * xys_foreach(struct xy_state *xs)
{
    void *y;
    unsigned yn;
    uint64_t xmax;
    uint64_t t_last;
    struct xarray *xy = xs->xy;

    t_last = xys_timens();
    yn = xs->y_null;
    y = NULL;
    xy_lock(xy, XY_LOCKR);

    if (xys_xrange_not(&xs->x_ranged, 0, 1))
        xys_xrange(xs, &t_last);
    for (xmax=xs->x_max; xs->x<=xmax; /**/) {
        y = xys_get_nolock(xs);
        xs->x += 1;

        if (xys_leaf_get(xs) || yn)
            break;
        xys_sleep(xs, &t_last, XY_LOCKR);
    }

    xy_unlock(xy, XY_LOCKR);
    return y;
}

struct xarray * 
xy_init(struct xarray *xy, unsigned flag, uint64_t ca)
{
    xy = xy_tryalloc(xy, flag);
    if (unlikely(!xy))
        return xy;
    xy->lock = xy_locker;
    xy_node_cache_init(xy, flag, ca);
    return xy;
}

void xy_close(struct xarray *xy)
{
    if (xy_cache_get(xy)) {
        pca_close(xy_canode(xy));
        pca_close(xy_caleaf(xy));
        pca_free(&xy_ca, xy);
        return ;
    }
    if (xy_heap_get(xy)) {
        free(xy);
        return ;
    }
    return ;
}
